package com.hfb.mashibing.alip8.diamondsquarealgorithm.class01;

import java.util.ArrayList;
import java.util.Stack;

/** 算法：单调栈
 * 问题1：
 *      在一个数组中，每一个位置的num，找到左边离num近的>num的值，
 *      和右边离num近的>num的值。要求时间复杂度O(n)。
 *
 * 思路：
 *      构建一个栈底到栈顶，从大到小的栈。遍历数组，将数组中的元素num依次压栈，
 *      同时保证栈中的元素币num大，如果num大于栈中的元素，则将栈中的元素弹出，
 *      同时记录弹出的元素的结果。num就是弹出元素右边离他近的大于它的，
 *      栈中它挨着的元素就是左边离他近的大于它的元素。一直出栈，直到栈中元素大于将要入栈的元素，
 *      或者栈为空时停止。当数组遍历完成后，栈中的元素依次弹出，
 *      此时它们弹出的元素的右边离它近的且大于它的元素为null，
 *      左边离它近的且大于它的元素为栈中下一个元素。
 *
 * 注意：当遇到两个相同的元素的时候，不弹出，将下标压在一起，弹出时一起弹出，同时更新它们左右比它们大的。
 */
public class Code03_MonotonousStack {

    public static class Num{
        public int left;
        public int right;
        public int val;

        public Num(int val){
            this.val = val;
        }
    }

    //这个node对象是为了处理重复的数的
    public static class Node{
        public int postion;
        public int counter;

        public Node(int postion){
            this.counter = 1;
            this.postion = postion;
        }
    }

    public static ArrayList<Num> monotonousStack(int[] arrays){
        if(arrays == null || arrays.length == 0) return null;
        Stack<Node> stack = new Stack<>();
        ArrayList<Num> res = new ArrayList<>();
        for(int i = 0; i < arrays.length; i++){
            while(!stack.isEmpty() && arrays[stack.peek().postion] < arrays[i]){
                Node t = stack.pop();
                //这些for循环是为了处理重复的数的，如果数组不重复，可以去掉
                for(int j = 0; j < t.counter; j++){
                    Num num = new Num(arrays[t.postion]);
                    num.left = stack.isEmpty() ? -1 : arrays[stack.peek().postion];
                    num.right = arrays[i];
                    res.add(num);
                }
            }
            if(!stack.isEmpty() && arrays[stack.peek().postion] == arrays[i])
                stack.peek().counter++;
            else
                stack.push(new Node(i));
        }
        while(!stack.isEmpty()){
            Node t = stack.pop();
            //这些for循环是为了处理重复的数的，如果数组不重复，可以去掉
            for(int j = 0; j < t.counter; j++){
                Num num = new Num(arrays[t.postion]);
                num.left = stack.isEmpty() ? -1 : arrays[stack.peek().postion];
                num.right = -1;
                res.add(num);
            }
        }
        return res;
    }

    public static void main(String[] args){
        int[] array = new int[]{5, 5, 4, 5 ,3, 6, 5, 3};
        ArrayList<Num> arrayList = new Code03_MonotonousStack().monotonousStack(array);
        for(Num num : arrayList){
            System.out.println(num.val + " 左边：" + num.left + "  右边：" + num.right);
        }
    }

}
